Path expressions can be used to specify values and structural constraints in XML queries. For example both XPath and XQuery, which are tools used to query or identify parts of an XML document, allow users to specify queries using path expressions. A branching path expression can be represented as a query tree, which is structurally matched against XML data. Performing this structural matching as efficiently as possible is one of the key issues in building an XML query engine. There are two common approaches to perform structural matching efficiently. One approach is to use a structural join, where a query tree is decomposed into a set of binary ancestor-descendant or parent-child relationships. The relationships are then evaluated using a binary merge join. Another approach is to use a holistic twig join, which processes a query tree with a single n-ary join.
Holistic twig joins are index-based, typically relying on an inverted index for positional information about XML elements. Cursors are used to access the inverted index and moved in a coordinated way to efficiently find structural matches. Holistic twig joins represent the state of the art for evaluating path expressions in XML queries. Generally, they are self-tuning and do not require a query optimizer. Because each cursor move in an inverted index can trigger I/O, the performance of a twig join is largely determined by how many cursor moves it makes. Yet, the existing twig join algorithms do not optimize along these lines. There has been more focus on minimizing the memory requirements of intermediate results than on minimizing the number of cursors moves. Accordingly, a new holistic twig join method that optimizes cursor movement  is desirable. Another shortcoming of existing twig join algorithms is that they assume all nodes in a query tree need to be output. However, an Xquery return clause often requires only a subset of the nodes being matched to be output. Accordingly, a new holistic twig join method that optimizes by only outputting the needed solution is desirable. Additional description of holistic twig join algorithm is provided in N. Bruno, N. Koudas, and D. Srivastava, Holistic twig joins: Optimal xml pattern matching, SIGMOD, 2002 (“Bruno et al.”); and H. Jiang, W. Wang, H. Lu, and J. Yu. Holistic twig joins on indexed xml documents, VLDB, 2003 (Jiang et al.), which disclosures are incorporated herein by reference.